package cn.com.algorithm.lru;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class LFUCache {

    private Map<String, Node> key_node;
    private Map<Integer, LinkedList<Node>> freq_list;
    private int capacity = 2;

    private int minFreq = 1;


    public int get(String key) {
        //If this number is not included, return - 1
        if (!key_node.containsKey(key)) return -1;
        Node node = key_node.get(key);
        //Get the frequency of the node
        int freq = node.freq;
        //Current node frequency plus 1
        node.freq += 1;
        //Deletes a node from the corresponding collection
        freq_list.get(freq).remove(node);
        //If the deleted node is 0, delete the collection
        if (freq_list.get(freq).size() == 0) {
            freq_list.remove(freq);
            if (freq == minFreq) {
                minFreq += 1;
            }
        }
        LinkedList<Node> list = freq_list.getOrDefault(freq + 1, new LinkedList<Node>());
        list.addFirst(node);
        freq_list.put(freq + 1, list);
        return node.value;
    }


    public void put(String key, int value) {
        if (capacity == 0) return;
        Node node = key_node.get(key);
        if (node != null) {
            //Gets the frequency of the current node
            int freq = node.freq;
            node.freq += 1;
            node.value = value;
            //Deletes a node from the set of corresponding frequency nodes
            freq_list.get(freq).remove(node);
            //If there are no elements in the collection, the collection is deleted
            if (freq_list.get(freq).size() == 0) {
                freq_list.remove(freq);
                //If the minimum frequency is deleted, add 1 to the minimum frequency
                if (freq == minFreq) {
                    minFreq += 1;
                }
            }
            //Move the node to the node set of the next frequency
            LinkedList<Node> list = freq_list.getOrDefault(freq + 1, new LinkedList<Node>());
            list.offerFirst(node);
            freq_list.put(freq + 1, list);
            key_node.put(key, node);
        } else {
            Node newNode = new Node(key, value, 1);
            //If the cache capacity is full, you need to delete the data that has been used the least frequently and has not been used for a long time
            if (key_node.size() == capacity) {
                Node lastNode = freq_list.get(minFreq).pollLast();
                key_node.remove(lastNode.key);
                if (freq_list.get(minFreq).size() == 0) {
                    freq_list.remove(minFreq);
                }
            }
            //Add a new node to the collection
            key_node.put(key, newNode);
            LinkedList<Node> list = freq_list.getOrDefault(1, new LinkedList<Node>());
            list.offerFirst(newNode);
            freq_list.put(1, list);
            minFreq = 1;
        }
    }

    public LFUCache(int capacity) {
        this.capacity = capacity;
        key_node = new HashMap<>();
        freq_list = new HashMap<>();
    }

    public LFUCache() {
        key_node = new HashMap<>();
        freq_list = new HashMap<>();
    }

    public static class Node {
        public String key;
        public int value;
        public int freq;

        public Node() {
        }

        public Node(String key, int value, int freq) {
            this.key = key;
            this.value = value;
            this.freq = freq;
        }
    }

    public static void main(String[] args) {
        LFUCache cache = new LFUCache(2);
        cache.put("key1", 1);    //1
        cache.put("key2", 2);    //21
        cache.put("key3", 3);    //32
        System.out.println(cache.get("key1"));
        System.out.println(cache.get("key2"));
        System.out.println(cache.get("key3"));
        cache.put("key1", 1);    //13
        System.out.println(cache.get("key1"));
        System.out.println(cache.get("key2"));
        System.out.println(cache.get("key3"));
        cache.put("key2", 2);    //21
        cache.put("key1", 1);    //12
    }
}